import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SumOf4Mum {
    /*
    * 四数之和
    * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
    * 请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
    * （若两个四元组元素一一对应，则认为两个四元组重复）：
    *
    * 0 <= a, b, c, d < n
    * a、b、c 和 d 互不相同
    * nums[a] + nums[b] + nums[c] + nums[d] == target
    * 你可以按 任意顺序 返回答案 。
    *
    * 1 <= nums.length <= 200
    * -10(9) <= nums[i] <= 10(9)
    * -10(9) <= target <= 10(9)
    * */
    public static void main(String[] args){
        SumOf4Mum sumOf4Mum = new SumOf4Mum();
        List<List<Integer>> lists = sumOf4Mum.mySolution(new int[]{1,-2,-5,-4,-3,3,3,5}, -11);
        System.out.println(lists);
    }

    // 我的想法：锚定第一个元素后，剩下的就是三数之和
    public List<List<Integer>> mySolution(int[] nums, int target){
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        //开始循环, 最外层时锚定的第一个元素
        for (int i = 0; i < nums.length - 3; i++) {
            // 排除没有结果的情况 这里不能直接用 nums[i] > target, 因为target不一定大于0，负数加负数会变小
            if(nums[i] > 0 && nums[i] > target) // 这里不能用 >= : nums = [0, 0, 0, 0], target = 0;
                return res;
            if(i > 0 && nums[i] == nums[i-1])
                continue;
            for (int j = i + 1; j < nums.length - 2; j++) {
                // 同理，这里不能直接写nums[j] > target - nums[i], 负数加负数能变小
                if(nums[j] > 0 && nums[j] > target - nums[i])
                    break; // 这里不能直接return, 因为还有外面一层i, 所有得用break
                // 去重i
                if(j > i + 1 && nums[j] == nums[j-1])
                    continue;
                int left = j + 1;
                int right = nums.length-1;
                while (left < right){
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum > target)
                        right--;
                    else if (sum < target)
                        left++;
                    else {
                        List<Integer> r = Arrays.asList
                                (nums[i], nums[j], nums[left], nums[right]);
                        res.add(r);
                        // 去重
                        while (left < right && nums[left] == nums[left+1]) left++;
                        while (left < right && nums[right] == nums[right-1]) right--;
                        left++;
                        right--;
                    }
                }
            }
        }
        return res;
    }
}
